package algorithm;

import java.util.*;

public class UnionFind {

    public static class Node<V>{
        public V value;
        public Node(V value) {
            this.value = value;
        }
    }

    public static class UnionSet<V> {
        public HashMap<V, Node<V>> nodes;
        public HashMap<Node<V>, Node<V>> parents;//记录每个节点的父点是什么，可能是代表节点，可能不是
        //作用：1、用于记录代表节点的代表集合的规模（合并时用到），2、得到集合的个数
        public HashMap<Node<V>, Integer> sizeMap;

        public UnionSet(List<V> values){
            for (V value : values) {
                Node<V> node = new Node<>(value);
                nodes.put(value, node);
                parents.put(node, node);
                sizeMap.put(node, 1);
            }
        }

        public Node<V> findFather(Node<V> cur){
            Stack<Node<V>> stack = new Stack<>();
            while(parents.get(cur) != cur){
                stack.push(cur);
                cur = parents.get(cur);
            }

            while(!stack.isEmpty()){
                parents.put(stack.pop(), cur);
            }

            return cur;
        }

        public boolean isSameSet(V a, V b){
            if(!nodes.containsKey(a) || !nodes.containsKey(b))
                return false;
            if(findFather(nodes.get(a)) == findFather(nodes.get(b)))
                return true;
            else
                return false;
        }

        public void union(V a, V b){
            if(!nodes.containsKey(a) || !nodes.containsKey(b))
                return;
            Node<V> aHead = findFather(nodes.get(a));
            Node<V> bHead = findFather(nodes.get(b));
            if(aHead != bHead){
                Integer aSetSize = sizeMap.get(aHead);
                Integer bSetSize = sizeMap.get(bHead);
                Node<V> big = aSetSize >= bSetSize? aHead : bHead;
                Node<V> small = big == aHead? bHead : aHead;
                parents.put(small, big);
                sizeMap.put(big, aSetSize + bSetSize);
                sizeMap.remove(small);
            }
        }

        public int getSetNum(){
            return sizeMap.size();
        }
    }

    public static class User{
        public String a;
        public String b;
        public String c;

        public User(String a, String b, String c) {
            this.a = a;
            this.b = b;
            this.c = c;
        }
    }

    public static int mergeUsers(List<User> users) {
        UnionSet<User> unionSet = new UnionSet<>(users);
        HashMap<String, User> aMap = new HashMap<>();
        HashMap<String, User> bMap = new HashMap<>();
        HashMap<String, User> cMap = new HashMap<>();
        for (User user : users) {
            if(!aMap.containsKey(user.a)){
                aMap.put(user.a, user);
            }else{
                unionSet.union(aMap.get(user.a), user);
            }
            if(!bMap.containsKey(user.b)){
                bMap.put(user.b, user);
            }else{
                unionSet.union(bMap.get(user.b), user);
            }
            if(!cMap.containsKey(user.c)){
                cMap.put(user.c, user);
            }else{
                unionSet.union(cMap.get(user.c), user);
            }
        }
        return unionSet.getSetNum();
    }

}
